iT邦幫忙

2021 iThome 鐵人賽

DAY 8
1
自我挑戰組

每日LeetCode解題紀錄系列 第 8

LeetCode解題 Day08

  • 分享至 

  • xImage
  •  

848. Shifting Letters

https://leetcode.com/problems/shifting-letters/


題目解釋

你有一個字串都是小寫的字串s ,還有一組偏移(shift)次數的陣列shifts

一次的shift 會將字母往下一個順序偏移,如 shift('a') = 'b', shift('t') = 'u', shift('z') = 'a'

而陣列shifts[i] = x 代表我們要將字串s 的前i+1 個字母偏移x

example

https://i.imgur.com/MdnkeCm.png


解法:

  1. 首先,這題要把字母做變化的話,用ASCII的代碼做計算應該是最方便的

  2. 再來,我們要計算各個字母需要偏移幾次,如example1a 是17次、b 是14次、c 是9次

  3. 最後,我們計算字串s的每個字母,記錄他已經從字母a 偏移幾次了,如a 偏移0次、b偏移1次、c偏移2次,這樣比較方便計算

  4. 最後的最後,我們就得到Time Limit Exceeded 的程式碼

程式碼

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        
        s_int = [ord(i) - 97 for i in s] #記錄從字母*a* 偏移幾次了
        
        shifts_sum = [sum(shifts[i:]) for i in range(len(shifts))] # 計算各個字母需要偏移幾次
        
        res = ''
        for i in range(len(s)):
            res += chr(97 + (s_int[i] + shifts_sum[i]) % 26) #別忘了modulo 26
            
        return res

可以過得解法:

LeetCode的很多題目若送出O(n^2)的解答通常就不會過

而上段程式碼的shifts_sum = [sum(shifts[i:]) for i in range(len(shifts))] 就是太花時間的原因,所以我們稍微改一下第二步的想法

example1a 要偏移17次,也就是3 + 5 + 9次
example1b 要偏移 8次,也就是 5 + 9次
example1c 要偏移 9次,也就是 9次

依照上面的規律,我們只需要先把shifts 做加總,再一項一項扣除掉不需要的次數就好

程式碼

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        
        s_int = [ord(i) - 97 for i in s]
        
        shifts_sum = sum(shifts)

        res = ''
        for i in range(len(s)):
            res += chr(97 + (s_int[i] + shifts_sum) % 26)
            shifts_sum -= shifts[i]
            
        return res

閒聊

今天的題目是難度Medium 的題目,寫起來不會很難

就只要多想一下怎麼避免迴圈包住迴圈的解法而已

今天是第8天,恭喜我自己完成一周的進度囉!/images/emoticon/emoticon34.gif


上一篇
LeetCode解題 Day07
下一篇
LeetCode解題 Day09
系列文
每日LeetCode解題紀錄30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0

恭喜完成一週的挑戰
/images/emoticon/emoticon42.gif

謝謝!
/images/emoticon/emoticon41.gif

我要留言

立即登入留言